home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Best of www.BestZips.com (Collector's Edition)
/
Best of WWW.BESTZIPS.COM Collector's Edition (JCSM Shareware) (JCS Marketing).ISO
/
prgtools
/
tn2.zip
/
DIJKSTRA.T
< prev
next >
Wrap
Text File
|
1996-11-15
|
4KB
|
196 lines
%
% "dijkstra.t" finds shortest path in a network by
% using Dijksta's algorithm
%
% Sample program for the T Interpreter by:
%
% Stephen R. Schmitt
% 962 Depot Road
% Boxborough, MA 01719
%
const N : int := 7
const Infinity : int := 2147483647
var G : array[N+1,N+1] of int
type mark : enum[ temporary, permanent ]
type vertex : record
prev : int
lnth : int
labl : mark
end record
var P : array[N+1] of vertex
program
var i, j, lnth, p : int
% step one
init_table
P[1].prev := 1
P[1].lnth := 0 % starting node is labeled with 0
P[1].labl := mark.permanent % starting node is permanently labeled
for i := 2...N do
P[i].prev := 1
P[i].lnth := G[1,i]
P[i].labl := mark.temporary
end for
loop
% step two
p := 0
lnth := Infinity
for i := 2...N do
if P[i].labl = mark.temporary then
if P[i].lnth < lnth then
p := i
lnth := P[i].lnth
end if
end if
end for
exit when p = 0
P[p].labl := mark.permanent
% step three
for i := 2...N do
if P[i].labl = mark.temporary then
for j := 2...N do
if P[j].lnth = Infinity or G[j,i] = Infinity then
lnth := Infinity
else
lnth := P[j].lnth + G[j,i]
end if
if P[i].lnth > lnth then
P[i].lnth := lnth
P[i].prev := j
end if
end for
end if
end for
end loop
% show resulting paths
for i := 1...N do
put "path from ", i, " to 1 has length of ", P[i].lnth
j := i
loop
put j
exit when j = 1
j := P[j].prev
end loop
end for
end program
%
% to: 1 2 3 4 5 6 7
% -------------------------------------
% 1| 0 # # # 1 4 #
% 2| # 0 # # 10 2 3
% 3| # # 0 # 7 6 5
% from: 4| # # # 0 # 8 7
% 5| 1 10 7 # 0 # #
% 6| 4 2 6 8 # 0 #
% 7| # 3 5 7 # # 0
%
procedure init_table
G[1,1] := 0
G[1,2] := Infinity
G[1,3] := Infinity
G[1,4] := Infinity
G[1,5] := 1
G[1,6] := 4
G[1,7] := Infinity
G[2,1] := Infinity
G[2,2] := 0
G[2,3] := Infinity
G[2,4] := Infinity
G[2,5] := 10
G[2,6] := 2
G[2,7] := 3
G[3,1] := Infinity
G[3,2] := Infinity
G[3,3] := 0
G[3,4] := Infinity
G[3,5] := 7
G[3,6] := 6
G[3,7] := 5
G[4,1] := Infinity
G[4,2] := Infinity
G[4,3] := Infinity
G[4,4] := 0
G[4,5] := Infinity
G[4,6] := 8
G[4,7] := 7
G[5,1] := 1
G[5,2] := 10
G[5,3] := 7
G[5,4] := Infinity
G[5,5] := 0
G[5,6] := Infinity
G[5,7] := Infinity
G[6,1] := 4
G[6,2] := 2
G[6,3] := 6
G[6,4] := 8
G[6,5] := Infinity
G[6,6] := 0
G[6,7] := Infinity
G[7,1] := Infinity
G[7,2] := 3
G[7,3] := 5
G[7,4] := 7
G[7,5] := Infinity
G[7,6] := Infinity
G[7,7] := 0
end procedure